package com.wyx.suanfa;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author 王艺锡
 * @version 1.0
 */
//前序和中序构造二叉树
public class buildTree2 {
    public static void main(String[] args) {
        //给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
        // inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
        String s1 = new String("abc");
        String s2 = new String("abc");
        System.out.println(s1 == s2);
        System.out.println(s1.equals(s2));

    }
}
/*
* class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(preorder,  0, preorder.length, inorder,0, inorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] preorder, int preBegin, int preEnd,
                            int[] inorder, int inBegin, int inEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || preBegin >= preEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
                            inorder, inBegin, rootIndex);
        root.right = findNode(preorder, preBegin + 1 + lenOfLeft, preEnd,
                            inorder, rootIndex + 1, inEnd);

        return root;
    }
}*/